import java.util.Arrays;

/**
 * 283. 移动零
 * https://leetcode-cn.com/problems/move-zeroes/
 */
public class Solutions_283 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};  // output: {1, 3, 12, 0, 0}
        moveZeroes(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 解法二：暴力法（5ms）
     */
    public static void moveZeroes2(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) {
                // 在 [i, len) 中找一个非零元素，进行替换
                for (int j = i + 1; j < len; j++) {
                    if (nums[j] != 0) {
                        // 交换
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        break;
                    }
                }
            }
        }
    }

    /**
     * 解法一：双指针，一次扫描（0ms）
     */
    public static void moveZeroes(int[] nums) {
        // 定义快慢指针，快指针在前，遍历 nums，慢指针在后，修改 nums
        int fast = 0, slow = 0, len = nums.length;
        while (fast < len) {
            if (nums[fast] != 0) {
                // 将非 0 元素，移动到 slow 索引上
                nums[slow++] = nums[fast];
            }
            fast ++;
        }
        while (slow < len) {
            // nums 遍历结束，slow 及之后的索引上，都为 0
            nums[slow++] = 0;
        }
    }
}